{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Longest Repeating Substring"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #binary-search #dynamic-programming #suffix-array #hash-function #rolling-hash"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #二分查找 #动态规划 #后缀数组 #哈希函数 #滚动哈希"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: longestRepeatingSubstring"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最长重复子串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定字符串&nbsp;<code>S</code>，找出最长重复子串的长度。如果不存在重复子串就返回 <code>0</code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>&quot;abcd&quot;\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>没有重复子串。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>&quot;abbaba&quot;\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>最长的重复子串为 &quot;ab&quot; 和 &quot;ba&quot;，每个出现 2 次。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>&quot;aabcaabdaab&quot;\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>最长的重复子串为 &quot;aab&quot;，出现 3 次。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>&quot;aaaaa&quot;\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>最长的重复子串为 &quot;aaaa&quot;，出现 2 次。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ol>\n",
    "\t<li>字符串&nbsp;<code>S</code>&nbsp;仅包含从&nbsp;<code>&#39;a&#39;</code> 到&nbsp;<code>&#39;z&#39;</code>&nbsp;的小写英文字母。</li>\n",
    "\t<li><code>1 &lt;= S.length &lt;= 1500</code></li>\n",
    "</ol>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [longest-repeating-substring](https://leetcode.cn/problems/longest-repeating-substring/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [longest-repeating-substring](https://leetcode.cn/problems/longest-repeating-substring/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"abcd\"', '\"abbaba\"', '\"aabcaabdaab\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        for i in range(1,len(s)):\n",
    "            if s[i-ans:i+1] in s[:i]:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        for i in range(1,len(s)):\n",
    "            if s[i-ans:i+1] in s[:i]:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        #Rabin-Karp harsh algorithm\n",
    "        def search(subString_length,letterNum,modulus,string_length, nums):\n",
    "            hash_enocode=0\n",
    "            for i in range(subString_length):\n",
    "                hash_enocode=(hash_enocode*letterNum+nums[i]) %modulus   \n",
    "            seen={hash_enocode}\n",
    "\n",
    "            aL= pow(letterNum,subString_length,modulus)\n",
    "            for start in range(1,string_length-subString_length+1):\n",
    "                hash_enocode=(hash_enocode*letterNum - nums[start-1]*aL+nums[start+subString_length-1])% modulus\n",
    "                if hash_enocode in seen:\n",
    "                    return start\n",
    "                seen.add(hash_enocode)\n",
    "            return -1\n",
    "\n",
    "        n=len(s)\n",
    "        nums=[ord(s[i])-ord('a') for i in range(n)]\n",
    "        a=26\n",
    "        modulus = 2**24\n",
    "\n",
    "        left, right=1,n\n",
    "        ans=0\n",
    "        while left<=right:\n",
    "            mid =left+(right-left)//2\n",
    "            if search(mid,a,modulus,n,nums)!=-1:\n",
    "                ans=mid\n",
    "                left=mid+1\n",
    "            else:\n",
    "                right=mid-1\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        def search(L):\n",
    "            seen = set()\n",
    "            h = 0\n",
    "            a = 26\n",
    "            al = pow(a, L, mod)\n",
    "\n",
    "            for i in range(L):\n",
    "                h = (h * a + ord(s[i])) % mod\n",
    "            \n",
    "            seen.add(h)\n",
    "\n",
    "            for i in range(1, len(s) - L + 1):\n",
    "                h = (h * a - ord(s[i - 1]) * al + ord(s[i + L - 1])) % mod\n",
    "\n",
    "                if h in seen:\n",
    "                    return i\n",
    "                seen.add(h)\n",
    "            \n",
    "            return -1\n",
    "        \n",
    "        left, right = 1, len(s)\n",
    "        mod = 10 ** 9 + 7\n",
    "        ans = 0\n",
    "\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            pos = search(mid)\n",
    "\n",
    "            if pos != -1:\n",
    "                ans = mid\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        #Rabin-Karp harsh algorithm\n",
    "        def search(subString_length,letterNum,modulus,string_length, nums):\n",
    "            hash_enocode=0\n",
    "            for i in range(subString_length):\n",
    "                hash_enocode=(hash_enocode*letterNum+nums[i]) %modulus   \n",
    "            seen={hash_enocode}\n",
    "\n",
    "            aL= pow(letterNum,subString_length,modulus)\n",
    "            for start in range(1,string_length-subString_length+1):\n",
    "                hash_enocode=(hash_enocode*letterNum - nums[start-1]*aL+nums[start+subString_length-1])% modulus\n",
    "                if hash_enocode in seen:\n",
    "                    return start\n",
    "                seen.add(hash_enocode)\n",
    "            return -1\n",
    "\n",
    "        n=len(s)\n",
    "        nums=[ord(s[i])-ord('a') for i in range(n)]\n",
    "        a=26\n",
    "        modulus = 2**24\n",
    "\n",
    "        left, right=1,n\n",
    "        ans=0\n",
    "        while left+1<right:\n",
    "            mid =left+(right-left)//2\n",
    "            if search(mid,a,modulus,n,nums)!=-1:\n",
    "                ans=mid\n",
    "                left=mid\n",
    "            else:\n",
    "                right=mid\n",
    "        if search(right,a,modulus,n,nums)!=-1:\n",
    "            return right\n",
    "        if search(left,a,modulus,n,nums)!=-1:\n",
    "            return left\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "_MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        d = [ord(c) - ord(\"a\") for c in s]\n",
    "        def verify(l: int) -> bool:\n",
    "            if l == 0:\n",
    "                return True\n",
    "            h = 0\n",
    "            for i in range(l):\n",
    "                h = (h * 26 + d[i]) % _MOD\n",
    "            seen = {h}\n",
    "            p = pow(26, l, _MOD)\n",
    "            for i in range(n - l):\n",
    "                h = (h * 26 - d[i] * p + d[l + i] + _MOD) % _MOD\n",
    "                if h in seen:\n",
    "                    return True\n",
    "                seen.add(h)\n",
    "            return False\n",
    "        \n",
    "        l, r = 0, n\n",
    "        while l < r:\n",
    "            m = l + r + 1 >> 1\n",
    "            if verify(m):\n",
    "                l = m\n",
    "            else:\n",
    "                r = m - 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        def kmp(s):\n",
    "            j = 0\n",
    "            next = [0]*len(s)\n",
    "            for i in range(1,len(s)):\n",
    "                while j > 0 and s[i] != s[j]:\n",
    "                    j = next[j-1]\n",
    "                if s[i] == s[j]:\n",
    "                    j += 1\n",
    "                next[i] = j\n",
    "            return next\n",
    "        m = 0\n",
    "        for i in range(len(s)):\n",
    "            now = max(kmp(s[i:]))\n",
    "            if now > m:\n",
    "                m = now\n",
    "        return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        def kmp(s):\n",
    "            j = 0\n",
    "            next = [0]*len(s)\n",
    "            for i in range(1,len(s)):\n",
    "                while j > 0 and s[i] != s[j]:\n",
    "                    j = next[j-1]\n",
    "                if s[i] == s[j]:\n",
    "                    j += 1\n",
    "                next[i] = j\n",
    "            return next\n",
    "        m = 0\n",
    "        for i in range(len(s)):\n",
    "            now = max(kmp(s[i:]))\n",
    "            if now > m:\n",
    "                m = now\n",
    "        return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def search(self, L: int, n: int, S: str) -> str:\n",
    "        \"\"\"\n",
    "        Search a substring of given length\n",
    "        that occurs at least 2 times.\n",
    "        @return start position if the substring exits and -1 otherwise.\n",
    "        \"\"\"\n",
    "        # seen = set()\n",
    "        # for start in range(0, n - L + 1):\n",
    "        #     tmp = S[start:start + L]\n",
    "        #     if tmp in seen:\n",
    "        #         return start\n",
    "        #     seen.add(tmp)\n",
    "        # return -1\n",
    "        seen = set()\n",
    "        for start in range(0, n - L + 1):\n",
    "            tmp = S[start : start + L]\n",
    "            h = hash(tmp)\n",
    "            if h in seen:\n",
    "                return start\n",
    "            seen.add(h)\n",
    "        return -1\n",
    "\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "\n",
    "        l, r = 1, n\n",
    "        while l < r:\n",
    "            L = l + (r - l) // 2\n",
    "            if self.search(L, n, s) != -1:\n",
    "                l = L + 1\n",
    "            else:\n",
    "                r = L\n",
    "        return l - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        def ok(t):\n",
    "            mp = {}\n",
    "            for i in range(0, n-t+1):\n",
    "                if s[i:i+t][::] in mp:\n",
    "                    return False\n",
    "                mp[s[i:i+t][::]] = True\n",
    "            return True\n",
    "        return bisect_left(range(1, n + 1), True, key=ok)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        def ok(t):\n",
    "            mp = {}\n",
    "            for i in range(0, n-t+1):\n",
    "                if s[i:i+t] in mp:\n",
    "                    return False\n",
    "                mp[s[i:i+t]] = True\n",
    "            return True\n",
    "        return bisect_left(range(1, n), True, key=ok)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        l,r=0,n-1\n",
    "        def check(mid):\n",
    "            if mid==0:return True\n",
    "            c=set()\n",
    "            for j in range(mid,n+1):\n",
    "                if s[j-mid:j]in c:return True\n",
    "                c.add(s[j-mid:j])\n",
    "            return False\n",
    "        res=0\n",
    "        while l<=r:\n",
    "            mid=(l+r)>>1\n",
    "            if check(mid):\n",
    "                res=mid\n",
    "                l=mid+1\n",
    "            else:\n",
    "                r=mid-1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        def ok(t):\n",
    "            mp = {}\n",
    "            for i in range(0, n-t+1):\n",
    "                if s[i:i+t] in mp:\n",
    "                    return False\n",
    "                mp[s[i:i+t]] = True\n",
    "            return True\n",
    "        return bisect_left(range(1, n), True, key=ok)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def search(self, L: int, n: int, S: str) -> str:\n",
    "        \"\"\"\n",
    "        Search a substring of given length\n",
    "        that occurs at least 2 times.\n",
    "        @return start position if the substring exits and -1 otherwise.\n",
    "        \"\"\"\n",
    "        seen = set()\n",
    "        for start in range(0, n - L + 1):\n",
    "            tmp = S[start:start + L]\n",
    "            if tmp in seen:\n",
    "                return start\n",
    "            seen.add(tmp)\n",
    "        return -1\n",
    "        \n",
    "    def longestRepeatingSubstring(self, S: str) -> str:\n",
    "        n = len(S)\n",
    "        \n",
    "        # binary search, L = repeating string length\n",
    "        left, right = 1, n\n",
    "        while left <= right:\n",
    "            L = left + (right - left) // 2\n",
    "            if self.search(L, n, S) != -1:\n",
    "                left = L + 1\n",
    "            else:\n",
    "                right = L - 1\n",
    "               \n",
    "        return left - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        def check(size) -> bool:\n",
    "            seen = set()\n",
    "            for l in range(len(s) - size + 1):\n",
    "                if s[l:l + size] in seen:\n",
    "                    return True\n",
    "                seen.add(s[l:l + size])\n",
    "            return False\n",
    "\n",
    "        l, r = 0, len(s)\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            if check(mid):\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def search(self, L: int, n: int, S: str) -> str:\n",
    "        \"\"\"\n",
    "        Search a substring of given length\n",
    "        that occurs at least 2 times.\n",
    "        @return start position if the substring exits and -1 otherwise.\n",
    "        \"\"\"\n",
    "        seen = set()\n",
    "        for start in range(0, n - L + 1):\n",
    "            tmp = S[start:start + L]\n",
    "            if tmp in seen:\n",
    "                return start\n",
    "            seen.add(tmp)\n",
    "        return -1\n",
    "        \n",
    "    def longestRepeatingSubstring(self, S: str) -> str:\n",
    "        n = len(S)\n",
    "        \n",
    "        # binary search, L = repeating string length\n",
    "        left, right = 1, n\n",
    "        while left <= right:\n",
    "            L = left + (right - left) // 2\n",
    "            if self.search(L, n, S) != -1:\n",
    "                left = L + 1\n",
    "            else:\n",
    "                right = L - 1\n",
    "               \n",
    "        return left - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        l, r = -1, n + 1\n",
    "\n",
    "        def find(l):\n",
    "            st = set()\n",
    "            for i in range(n - l + 1):\n",
    "                sub = s[i: i + l]\n",
    "                if sub in st:\n",
    "                    return True\n",
    "                st.add(sub)\n",
    "            return False\n",
    "\n",
    "        while l + 1 < r:\n",
    "            m = (l + r) // 2\n",
    "            if find(m):\n",
    "                l = m\n",
    "            else:\n",
    "                r = m\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def search(self, L: int, n: int, S: str) -> str:\n",
    "        \"\"\"\n",
    "        Search a substring of given length\n",
    "        that occurs at least 2 times.\n",
    "        @return start position if the substring exits and -1 otherwise.\n",
    "        \"\"\"\n",
    "        seen = set()\n",
    "        for start in range(0, n - L + 1):\n",
    "            tmp = S[start:start + L]\n",
    "            if tmp in seen:\n",
    "                return start\n",
    "            seen.add(tmp)\n",
    "        return -1\n",
    "        \n",
    "    def longestRepeatingSubstring(self, S: str) -> str:\n",
    "        n = len(S)\n",
    "        \n",
    "        # binary search, L = repeating string length\n",
    "        left, right = 1, n\n",
    "        while left <= right:\n",
    "            L = left + (right - left) // 2\n",
    "            if self.search(L, n, S) != -1:\n",
    "                left = L + 1\n",
    "            else:\n",
    "                right = L - 1\n",
    "               \n",
    "        return left - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        def check(t):\n",
    "            mp = {}\n",
    "            for i in range(0, n-t+1):\n",
    "                if s[i:i+t][::] in mp:\n",
    "                    return True\n",
    "                mp[s[i:i+t][::]] = True\n",
    "            return False\n",
    "        lo, hi = 1, n\n",
    "        while lo < hi:\n",
    "            mid = (lo + hi) >> 1\n",
    "            if not check(mid):\n",
    "                hi = mid\n",
    "            else:\n",
    "                lo = mid + 1\n",
    "        return lo - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        def search(k):\n",
    "            # print(f\"call({k})\")\n",
    "            visited = set()\n",
    "            for i in range(len(s)-k+1):\n",
    "                if s[i:i+k] in visited:\n",
    "                    return True\n",
    "                else:\n",
    "                    visited.add(s[i:i+k])\n",
    "            return False\n",
    "\n",
    "        low = 1\n",
    "        high = len(s)-1\n",
    "        ans = 0\n",
    "        while low <= high:\n",
    "            mid = (low+high)//2\n",
    "            if search(mid):\n",
    "                ans = mid\n",
    "                low = mid + 1\n",
    "            else:\n",
    "                high = mid - 1\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        \n",
    "        def check(S,res):\n",
    "            record = set([S[i:i+res] for i in range(len(S)-res+1)])\n",
    "            print((len(record) != len(S)-res+1))\n",
    "            return (len(record) != len(S)-res+1)\n",
    "        S = s\n",
    "        left = 1\n",
    "        right = len(S)-1\n",
    "        while left <= right:\n",
    "            #print(left,right)\n",
    "            mid = (left+right+1)//2\n",
    "            if check(S,right):\n",
    "                return right\n",
    "            else:\n",
    "                if check(S,mid):\n",
    "                    left = mid\n",
    "                else:\n",
    "                    right = mid-1\n",
    "        return 0         \n",
    "\n",
    "\n",
    "        n = len(s)\n",
    "        for k in range(n - 1, 0, -1):\n",
    "            pre = set()\n",
    "            for i in range(n - k + 1):\n",
    "                if s[i: i + k] in pre:\n",
    "                    return k\n",
    "                pre.add(s[i: i + k])\n",
    "        return 0\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ln = 0\n",
    "        low, high = ln, n - 1\n",
    "\n",
    "        def f(x):\n",
    "            seen = set()\n",
    "            for i in range(n - x + 1):\n",
    "                tmp = s[i: i + x]\n",
    "                if tmp in seen:\n",
    "                    return True \n",
    "                seen.add(tmp)\n",
    "            return False \n",
    "        \n",
    "        while low <= high:\n",
    "            mid = (low + high) // 2\n",
    "            if f(mid):\n",
    "                low = mid + 1\n",
    "                ln = mid \n",
    "            else:\n",
    "                high = mid - 1\n",
    "        return ln \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        l, r = 0, n - 1\n",
    "        while l <= r and r > 0:\n",
    "            mid = l + (r - l) // 2\n",
    "            if self.check(mid, s, n) == -1:\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return r\n",
    "\n",
    "    def check(self, L, s, n):\n",
    "        hashSet = set()\n",
    "        for i in range(n - L + 1):\n",
    "            if s[i:i + L] in hashSet:\n",
    "                return i\n",
    "            else:\n",
    "                hashSet.add(s[i:i + L])\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "a b c a b c\n",
    "1 2 3 4 5 6\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        left, right = 1, len(s)\n",
    "\n",
    "        def search(mid):\n",
    "            visited = set()\n",
    "\n",
    "            for i in range(len(s) - mid + 1):\n",
    "                temp = s[i :mid + i]\n",
    "                if temp in visited:\n",
    "                    return i\n",
    "                visited.add(temp)\n",
    "\n",
    "            return -1\n",
    "\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            # 找到一个repeating substring, 就往后面找看看有没有更长的substring\n",
    "            if search(mid) != -1:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        \n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        def check(n):\n",
    "            D = set()\n",
    "            for i in range(len(s)-n+1):\n",
    "                if s[i:i+n] in D:\n",
    "                    return True\n",
    "                D.add(s[i:i+n])\n",
    "            return False\n",
    "        N = len(s)\n",
    "        start, end = 1, N\n",
    "        ans = 0\n",
    "        while start < end:\n",
    "            mid = start + (end - start) // 2\n",
    "            if check(mid):\n",
    "                ans = mid\n",
    "                start = mid + 1\n",
    "            else:\n",
    "                end = mid - 1\n",
    "        if check(start):\n",
    "            ans = start\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        @lru_cache(None)\n",
    "        def check(k):\n",
    "            pre = set()\n",
    "            for i in range(n - k + 1):\n",
    "                cur = s[i: i + k]\n",
    "                if cur in pre:\n",
    "                    return True\n",
    "                pre.add(cur)\n",
    "            return False\n",
    "\n",
    "        n = len(s)\n",
    "        low = 1\n",
    "        high = n - 1\n",
    "        while low < high - 1:\n",
    "            mid = low + (high - low) // 2\n",
    "            if check(mid):\n",
    "                low = mid\n",
    "            else:\n",
    "                high = mid\n",
    "        if check(high):\n",
    "            return high\n",
    "        if check(low):\n",
    "            return low\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        for ln in range(n - 1, 1, -1):\n",
    "            cnt = Counter()\n",
    "            for i in range(n - ln + 1):\n",
    "                cnt[s[i: i + ln]] += 1\n",
    "            mx = max(cnt.values())\n",
    "            if mx > 1:\n",
    "                return ln \n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        for k in range(n - 1, 0, -1):\n",
    "            pre = set()\n",
    "            for i in range(n - k + 1):\n",
    "                if s[i: i + k] in pre:\n",
    "                    return k\n",
    "                pre.add(s[i: i + k])\n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        def search(k):\n",
    "            # print(f\"call({k})\")\n",
    "            visited = set()\n",
    "            for i in range(len(s)-k+1):\n",
    "                if s[i:i+k] in visited:\n",
    "                    return True\n",
    "                else:\n",
    "                    visited.add(s[i:i+k])\n",
    "            return False\n",
    "\n",
    "        \n",
    "        for k in range(len(s)-1, -1, -1):\n",
    "            if search(k):\n",
    "                return k\n",
    "\n",
    "        return 0\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class suffix_array:\n",
    "    def __init__(self, n: int, m: int, s):\n",
    "        self.N = 10 ** 5 + 10\n",
    "        self.n = n\n",
    "        self.m = m                                  #最大的字母，ascii码\n",
    "        self.s = s\n",
    "        self.sa = [0 for _ in range(self.N)]         #排名为i的后缀，开头的index（从1开始计）\n",
    "        self.rk = [0 for _ in range(self.N)]         #当前长度下，i开始的后缀的，排名\n",
    "        self.height = [0 for _ in range(self.N)]     #rk是i-1 和 i 的lcp\n",
    "        self.x = [0 for _ in range(self.N)]\n",
    "        self.y = [0 for _ in range(self.N)]\n",
    "        self.c = [0 for _ in range(self.N)]\n",
    "    \n",
    "    def get_sa(self) -> None:\n",
    "        for i in range(1, self.n + 1):\n",
    "            self.x[i] = ord(self.s[i])\n",
    "            self.c[self.x[i]] += 1\n",
    "        for i in range(2, self.m + 1):  self.c[i] += self.c[i - 1]\n",
    "        for i in range(self.n, 0, -1):\n",
    "            self.sa[self.c[self.x[i]]] = i\n",
    "            self.c[self.x[i]] -= 1\n",
    "        \n",
    "        k = 1\n",
    "        while k <= self.n: \n",
    "            num = 0\n",
    "            for i in range(self.n - k + 1, self.n + 1, 1):\n",
    "                num += 1\n",
    "                self.y[num] = i\n",
    "            for i in range(1, self.n + 1):\n",
    "                if self.sa[i] > k:\n",
    "                    num += 1\n",
    "                    self.y[num] = self.sa[i] - k\n",
    "            \n",
    "            for i in range(1, self.m + 1):  self.c[i] = 0\n",
    "            for i in range(1, self.n + 1):  self.c[self.x[i]] += 1\n",
    "            for i in range(2, self.m + 1):  self.c[i] += self.c[i - 1]\n",
    "            \n",
    "            for i in range(self.n, 0, -1):\n",
    "                self.sa[self.c[self.x[self.y[i]]]] = self.y[i]\n",
    "                self.c[self.x[self.y[i]]] -= 1\n",
    "                self.y[i] = 0\n",
    "            \n",
    "            self.x, self.y = self.y, self.x\n",
    "            self.x[self.sa[1]] = 1\n",
    "            num = 1\n",
    "\n",
    "            for i in range(2, self.n + 1):\n",
    "                if (self.y[self.sa[i]] == self.y[self.sa[i - 1]]) and (self.y[self.sa[i] + k] == self.y[self.sa[i - 1] + k]):\n",
    "                    self.x[self.sa[i]] = num\n",
    "                else:\n",
    "                    num += 1\n",
    "                    self.x[self.sa[i]] = num\n",
    "\n",
    "            if num == self.n:\n",
    "                break\n",
    "            self.m = num\n",
    "\n",
    "            k *= 2\n",
    "\n",
    "    def get_height(self) -> None:\n",
    "        for i in range(1, self.n + 1):\n",
    "            self.rk[self.sa[i]] = i\n",
    "        k = 0\n",
    "        for i in range(1, self.n + 1):\n",
    "            if self.rk[i] == 1:\n",
    "                continue\n",
    "            if k > 0:\n",
    "                k -= 1\n",
    "            j = self.sa[self.rk[i] - 1]\n",
    "            while (i + k <= self.n) and (j + k <= self.n) and (self.s[i + k] == self.s[j + k]):\n",
    "                k += 1\n",
    "            self.height[self.rk[i]] = k\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        n = len(s)\n",
    " \n",
    "        SA = suffix_array(n, ord('z'), \" \" + s)     \n",
    "        SA.get_sa()\n",
    "        SA.get_height()\n",
    "\n",
    "        res = 0\n",
    "        for i in range(2, n + 1):\n",
    "            if SA.height[i] > res:\n",
    "                res = SA.height[i]\n",
    "  \n",
    "        return res\n",
    "\n",
    "# 作者：HanXin\n",
    "# 链接：https://leetcode.cn/problems/longest-repeating-substring/solutions/635439/c-python-3-quan-shi-tao-lu-biao-zhun-er-vbgss/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        f = [[0]*n for _ in range(n)]\n",
    "        res = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                if s[i]==s[j]:\n",
    "                    f[i][j] = f[i-1][j-1]+1\n",
    "                    res = max(res, f[i][j])\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[None] * n for _ in range(n)]\n",
    "        res = 0\n",
    "        for i in range(n - 1):\n",
    "            for j in range(i + 1, n):\n",
    "                if s[i] == s[j]:\n",
    "                    if i == 0:\n",
    "                        dp[i][j] = 1\n",
    "                    else:\n",
    "                        #print(i, j, dp[i][j], dp[i - 1][j - 1])\n",
    "                        dp[i][j] = dp[i - 1][j - 1] + 1\n",
    "                else:\n",
    "                        dp[i][j] = 0\n",
    "\n",
    "                res = max(res, dp[i][j])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        res = 0\n",
    "        for i in range(n - 1):\n",
    "            for j in range(i + 1, n):\n",
    "                if s[i] == s[j]:\n",
    "                    if i == 0:\n",
    "                        dp[i][j] = 1\n",
    "                    else:\n",
    "                        dp[i][j] = dp[i - 1][j - 1] + 1\n",
    "                res = max(res, dp[i][j])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        dp=[[0 for j in range(n)] for i in range(n)]\n",
    "        ans=0\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                if s[i]==s[j]:\n",
    "                    if i==0:dp[i][j]=1\n",
    "                    else:dp[i][j]=dp[i-1][j-1]+1\n",
    "                ans=max(ans,dp[i][j])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "\n",
    "        dp = [[0 for j in range(len(s))] for i in range(len(s))]\n",
    "        ans = 0\n",
    "        for i in range(len(s)):\n",
    "            for j in range(i+1,len(s)): # j至少等于i+1，这样两个子串必定是不完全重叠的\n",
    "                if s[i]==s[j]:\n",
    "                    dp[i][j]=dp[i-1][j-1]+1 if i else 1\n",
    "                    ans = max(ans,dp[i][j]) # 最终答案可能落在任意位置，因此实时更新\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        dp=[[0 for j in range(n)] for i in range(n)]\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                if s[i]==s[j]:\n",
    "                    if i==0:dp[i][j]=1\n",
    "                    else:dp[i][j]=dp[i-1][j-1]+1\n",
    "                ans=max(ans,dp[i][j])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "\n",
    "        dp = [[0 for j in range(len(s))] for i in range(len(s))]\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(len(s)):\n",
    "            for j in range(i+1, len(s)):\n",
    "                if s[i] == s[j]:\n",
    "                    dp[i][j] = dp[i-1][j-1]+1 if i else 1\n",
    "                    ans = max(ans, dp[i][j])\n",
    "        \n",
    "        \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        dp = [[0 for j in range(len(s))] for _ in range(len(s))]\n",
    "        ans = 0 \n",
    "        for i in range(len(s)):\n",
    "            for j in range(i + 1, len(s)):\n",
    "                if s[i] == s[j]:\n",
    "                    dp[i][j] = dp[i-1][j-1] + 1 if i else 1\n",
    "                    ans = max(ans, dp[i][j])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        dp = [[0 for j in range(len(s))] for i in range(len(s))]\n",
    "        ans = 0\n",
    "        for i in range(len(s)):\n",
    "            for j in range(i+1, len(s)):\n",
    "                if s[i] == s[j]:\n",
    "                    dp[i][j] = dp[i-1][j-1] + 1 if i else 1\n",
    "                    ans = max(ans, dp[i][j])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        dp = [[0 for i in range(len(s))] for j in range(len(s))]\n",
    "        ans = 0\n",
    "        for i in range(len(s)):\n",
    "            for j in range(i+1, len(s)):\n",
    "                if s[i] == s[j]:\n",
    "                    dp[i][j] = dp[i-1][j-1] + 1 if i else 1\n",
    "                ans = max(ans, dp[i][j])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        s1,s2 = copy.deepcopy(s),copy.deepcopy(s)\n",
    "        n,m = len(s1),len(s2)\n",
    "        dp = [[0]*(m+1) for i in range(n+1)]\n",
    "\n",
    "        mmax = 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if s1[i]==s2[j] and i!=j:\n",
    "                    dp[i+1][j+1] = dp[i][j]+1\n",
    "                    if dp[i+1][j+1]>mmax:\n",
    "                        mmax = dp[i+1][j+1]\n",
    "        \n",
    "        return mmax\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, S: str) -> int:\n",
    "        from collections import defaultdict\n",
    "        mem = defaultdict(lambda: 0, {})\n",
    "        length = len(S)\n",
    "        for i in range(1, length + 1):\n",
    "            for j in range(i+1, length + 1):\n",
    "                if S[i-1] == S[j-1]:\n",
    "                    mem[i, j] = mem[i -1, j-1] + 1\n",
    "        values = [0] + list(mem.values())\n",
    "        return max(values)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        tree = {}\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(len(s)):\n",
    "            cur = tree\n",
    "            cnt = 0\n",
    "            for c in s[i:]:\n",
    "                if c in cur:\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    cur[c] = {}\n",
    "                cur = cur[c]\n",
    "            ans = max(ans, cnt)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        tree = {}\n",
    "        ans = 0\n",
    "        n = len(s)\n",
    "\n",
    "        for i in range(n):\n",
    "            if n-i <= ans:\n",
    "                break\n",
    "\n",
    "            cur = tree\n",
    "            cnt = 0\n",
    "            for c in s[i:]:\n",
    "                if c in cur:\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    cur[c] = {}\n",
    "                cur = cur[c]\n",
    "            if cnt > ans:\n",
    "                ans = cnt\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        tree = {}\n",
    "        ans = 0\n",
    "        n = len(s)\n",
    "\n",
    "        for i in range(n):\n",
    "            if n-i <= ans:\n",
    "                break\n",
    "\n",
    "            cur = tree\n",
    "            cnt = 0\n",
    "            for c in s[i:]:\n",
    "                if c in cur:\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    cur[c] = {}\n",
    "                cur = cur[c]\n",
    "            ans = max(ans, cnt)\n",
    "        \n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
